package b.设计题;

import java.util.Map;
import java.util.HashMap;
import java.util.LinkedHashMap;

public class LFUCache {
    int capacity;
    Map<Integer,Integer> kv_map = new HashMap<Integer,Integer>();
    //用LinkedHasMap实现LRU（最近最少使用），当存在平局（即两个或更多个键具有相同使用频率）
    Map<Integer,Integer> freq_map = new LinkedHashMap<Integer,Integer>();
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        //如果key不存在：
        if (!kv_map.containsKey(key)) {
            //返回-1
            return -1;
        }
        //如果key存在：
        else{
            //从访问频率i的链表中移除，放到频率i+1的链表中
            int freq = freq_map.remove(key);
            //返回对应的value，并将元素的访问频率+1
            freq_map.put(key, freq + 1);
            return kv_map.get(key);
        }
    }

    public void put(int key, int value) {
        //如果key已经存在：
        if(kv_map.containsKey(key)){
            //从访问频率i的链表中移除，放到频率i+1的链表中
            int freq = freq_map.remove(key);
            //修改对应的value，并将访问频率+1
            freq_map.put(key,freq+1);
            kv_map.put(key,value);
        }
        //如果key不存在：
        else{
            //若缓存超过最大容量：
            //先删除访问频率最低的元素（遍历freq_map, 找到最小的freq值，从2个map中删除）
            if(kv_map.size() >= capacity){
                int min = Integer.MAX_VALUE;//记录最小的freq值
                int key3 = key;//记录最小freq值独影的key
                for(int key2 : freq_map.keySet()){
                    if(min > freq_map.get(key2)){
                        min = freq_map.get(key2);
                        key3 = key2;
                    }
                }
                //for找完频率最低的元素，删除！
                kv_map.remove(key3);
                freq_map.remove(key3);
            }
            //再插入访问频率为1的新元素 （没超过最大容量，直接执行本下方）
            kv_map.put(key,value);
            freq_map.put(key,1);
        }
    }

}

